 package Lecture9;

import java.security.acl.Permission;
import java.util.Arrays;

public class heapExer {

	public static void main(String[] args) 
	{

		int[] arr = {2,4,3,5,1,9,8};
		System.out.println(Arrays.toString(arr));
		//arr = buildHeap(arr);
	    //System.out.println(Arrays.toString(arr));
		//arr = sortHeap(arr);
		//System.out.println(Arrays.toString(sortHeap(arr)));
		sortHeap(arr);
		
	}
	
	public static int[] buildHeap (int[]  arr)
	{
		for(int i = 0; i < arr.length; i++)
		{
			int nodeIndex = i;
			
			while( nodeIndex != 0)
			{
				int parentIndex = (nodeIndex-1) /2;
				
				if(arr[parentIndex] < arr[nodeIndex])
				{
					int temp = arr[parentIndex];
					arr[parentIndex] = arr[nodeIndex];
					arr[nodeIndex] = temp;
				}
				nodeIndex = parentIndex;
				
			}
			
		}
		
		return arr;
	}

	
	public static void sortHeap ( int[] arr)
	{
		buildHeap(arr);
		
		
		for(int i = 0; i < arr.length; i++)
		{
			int parentIndex = 0;
			swap(arr, 0, arr.length-1-i);
			int heapSize = arr.length-1-i;

			
			while(true)
			{
				int leftChildInd = parentIndex*2 + 1;
				int rightChildInd = parentIndex*2 + 2;
 			
				if (leftChildInd >= heapSize)								//no child's
				{
					break;
				}
				else 
					if (rightChildInd >= heapSize)                        //only left
					{
						if (arr[leftChildInd] > arr[parentIndex])
						{
							swap(arr, leftChildInd, parentIndex);
						}
						break;
					}
					else												// two child's
						if(arr[leftChildInd] > arr[rightChildInd])
						{
						
							if(arr[leftChildInd] > arr[parentIndex])		// left bigger than parent
							{
								swap(arr, leftChildInd, parentIndex);
							}
							parentIndex = leftChildInd;
						}
							else
							{
								if(arr[rightChildInd] > arr[parentIndex])
								{
									swap(arr, rightChildInd, parentIndex);
								}
							parentIndex = rightChildInd;

							}
				
			
		}
		
		
		}
		
		System.out.println(Arrays.toString(arr));
	
	}

	private static void swap(int[] arr, int i, int j) 
	{
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
		
	}
	
	
	
}
